//
// Created by hitfy on 2018/4/22.
//

/**
 * 项目需要使用OpenCV，相关配置可以参考https://blog.csdn.net/qq_33653424/article/details/79824457
 *
 * 环境配置：
 * Debian/Ubuntu终端输入：
    sudo apt-get install libopencv-dev python-opencv     #安装opencv开发库

    sudo /bin/bash -c 'echo "/usr/local/lib" > /etc/ld.so.conf.d/opencv.conf'    #将opencv库文件所在路径导入ld配置
    sudo ldconfig    #更新配置
    sudo gedit /etc/profile
    在文件的末尾添加 export PKG_CONFIG_PATH="$PKG_CONFIG_PATH:/usr/local/lib/pkgconfig"    #将pkgconfig加入环境变量
    source /etc/profile    #更新环境变量
 *
 * 编译设置：
 * 在CMakeLists.txt中添加：
    add_executable(xxx xxx.cpp)     #xxx.cpp即为使用了opencv的源文件，xxx为可执行文件名称
    find_package( OpenCV REQUIRED )
    include_directories( ${OpenCV_INCLUDE_DIRS} )
    target_link_libraries( xxx ${OpenCV_LIBS} )     #xxx为可执行文件名称
 */
#include <bits/stdc++.h>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;//包含cv命名空间

vector<pair<int, int>> nodes;
vector<pair<int, int>> originNodes;

static int nodeSize = 5000;

void createRandomNodes(){
    set<pair<int, int>> nodeset;
    int times = 0;
    while(nodeset.size() < nodeSize){
        nodeset.insert(pair<int, int>(rand() % 100, rand() % 100));
        times++;
    }
    nodes.clear();
    originNodes.clear();
    copy(nodeset.begin(), nodeset.end(), back_inserter(nodes));
    copy(nodeset.begin(), nodeset.end(), back_inserter(originNodes));
    printf("The times of generating random points:%d\n", times);
}

void printNodes(vector<pair<int, int>> &nodes){
    printf("nodes number:\t%ld\n", nodes.size());
    vector<pair<int, int>>::iterator it = nodes.begin();
    while(it != nodes.end()){
        printf("(%d, %d), ", it->first, it->second);
        it++;
    }
    printf("\n");
}

//三角形内部的点与三个顶点的向量间互相叉乘时结果同号
bool isinside(int it1, int it2, int it3, int it4){
    pair<int, int> PA(nodes[it1].first - nodes[it4].first, nodes[it1].second - nodes[it4].second);
    pair<int, int> PB(nodes[it2].first - nodes[it4].first, nodes[it2].second - nodes[it4].second);
    pair<int, int> PC(nodes[it3].first - nodes[it4].first, nodes[it3].second - nodes[it4].second);
    int t1 = PA.first * PB.second - PA.second * PB.first;
    int t2 = PB.first * PC.second - PB.second * PC.first;
    int t3 = PC.first * PA.second - PC.second * PA.first;
    return t1*t2 > 0 && t1*t3 > 0;
}

void convexHull_Enum(){
    if(nodes.size() <= 3)
        return;
    for(int it1 = 0; it1 < nodes.size(); it1++){
        for(int it2 = it1 + 1; it2 < nodes.size(); it2++){
            for(int it3 = it2 + 1; it3 < nodes.size(); it3++){
                if(nodes[it1].first == nodes[it2].first && nodes[it1].first == nodes[it3].first)
                    continue;
                if(nodes[it1].second == nodes[it2].second && nodes[it1].second == nodes[it3].second)
                    continue;
                vector<pair<int, int>>::iterator it = nodes.begin();
                for(int it4 = 0; it4 < nodes.size(); it4++) {
                    if(it4 != it1 && it4 != it2 && it4 != it3 && isinside(it1, it2, it3, it4)) {
//                            printf("Erase point:%d, %d\t%d:%d, %d\t%d:%d, %d\t%d:%d, %d\t%d:%d, %d\n",
//                                   it->first, it->second,
//                                   it1, nodes[it1].first, nodes[it1].second,
//                                   it2, nodes[it2].first, nodes[it2].second,
//                                   it3, nodes[it3].first, nodes[it3].second,
//                                   it4, nodes[it4].first, nodes[it4].second);
                            nodes.erase(it);
                            if(it1 > it4)
                                it1--;
                            if(it2 > it4)
                                it2--;
                            if(it3 > it4)
                                it3--;
                    }
                    it++;
                }
            }
        }
    }
}
int main() {
    printf("Input Size(options:1000/2000/3000/4000/5000):");
    scanf("%d", &nodeSize);
    clock_t startTime,endTime;
    createRandomNodes();
    startTime = clock();
    convexHull_Enum();
    endTime = clock();
    printf("%ld\t%ld\t%ld\n", startTime, endTime, CLOCKS_PER_SEC);
    printf("Algorithm run time:\t%lfms\n", (double)(endTime - startTime) / CLOCKS_PER_SEC * 1000);
    printNodes(originNodes);
    printNodes(nodes);

    int w = 600;
    int pw = w / 100;
    Mat image( w, w, CV_8UC3, Scalar(255,255,255));
    //绘制网格
//    for(int i = 0; i < w/6; i++) {
//        line(image, Point(pw * i, 0), Point(pw*i, w), Scalar( 0, 0, 0 ));
//        line(image, Point(0, pw*i), Point(w, pw*i), Scalar( 0, 0, 0 ));
//    }
    for(int i = 0; i < originNodes.size(); i++)//绘制所有原始点并标为绿色
        circle( image, Point( originNodes[i].first * pw, originNodes[i].second * pw), 3, Scalar( 0, 255, 0 ), -1, 8);
    for(int i = 0; i < nodes.size(); i++)//绘制凸包点并标为红色
        circle( image, Point( nodes[i].first * pw, nodes[i].second * pw), 3, Scalar( 0, 0, 255 ), -1, 8);
    imshow( "ConvexHull_Enum: " + to_string(nodeSize) + " points", image);
    waitKey();
    return 0;
}